package cn.com.algorithm.lru;
import java.util.HashMap;
import java.util.Map;

/**
 * 使用自定义链表实现LRU
 */
public class LRUCache1 {
    //Define map mapping
    private Map<String, Node> map;
    //Define cache capacity
    private int capacity = 8;
    //There is currently a data in the cache
    private int size = 0;
    //Head node and tail node of linked list
    private Node head, tail;

    //Read data from cache
    public int get(String key) {
        Node node = map.get(key);
        //If it can be found, move the node to the head of the linked list without returning - 1
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    //Add node to cache
    public void put(String key, int value) {
        if(capacity == 0)   return;
        Node node = map.get(key);
        if (node != null) {
            //If it exists, modify the value of this point and move it to the head of the linked list
            node.value = value;
            moveToHead(node);
            return;
        }

        //If it does not exist, first judge whether the cache space is sufficient
        if (size == capacity) {
            map.remove(tail.pre.key);
            deleteNode(tail.pre);
            size -= 1;
        }
        Node newNode = new Node(key, value);
        addToHead(newNode);
        map.put(key, newNode);
        size += 1;
    }

    //Move node to head node
    private void moveToHead(Node node) {
        deleteNode(node);
        addToHead(node);
    }

    //Add node to header
    private void addToHead(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    //Delete this node
    private void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public LRUCache1(int capacity) {
        this.capacity = capacity;
        initLinkedList();
        map = new HashMap<>(capacity);
        size = 0;
    }

    //Initialize linked list
    private void initLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public LRUCache1() {
        initLinkedList();
        map = new HashMap<>(this.capacity);
    }

    public static class Node {
        public Node pre;
        public Node next;

        public String key;
        public int value;

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }



    public static void main(String[] args) {
        LRUCache1 cache = new LRUCache1(2);
        cache.put("key1", 1);
        cache.put("key2", 2);
        System.out.println(cache.get("key2"));//21
        cache.put("key3", 3);
        System.out.println(cache.get("key1"));//32
    }

}